/*
 * Copyright Aduna (http://www.aduna-software.com/) (c) 1997-2007.
 *
 * Licensed under the Aduna BSD-style license.
 */

package edu.tju.commons.collections;

import java.lang.reflect.Array;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * A simple Map implementation, taking roughly the same strategy as ArrayList,
 * resulting in a memory-efficient and (for small amounts of key-value pairs)
 * fast implementation.
 */
public class ArrayMap<K, V> implements Map<K, V> {

	private K[] keys;

	private V[] values;

	private int size;

	private int modCount;

	/**
	 * Create a new ArrayMap with an initial capacity of 0.
	 */
	public ArrayMap() {
		this(0);
	}

	/**
	 * Create new ArrayMap with the specified initial capacity.
	 * 
	 * @param initialCapacity
	 *            the initial capacity of the internal arrays
	 */
	@SuppressWarnings("unchecked")
	public ArrayMap(int initialCapacity) {
		keys = (K[]) new Object[initialCapacity];
		values = (V[]) new Object[initialCapacity];
		size = 0;
		modCount = 0;
	}

	/**
	 * Create a new ArrayMap that contains the same mappings as the specified
	 * map. Its capacity will be equal to the size of the specified.
	 * 
	 * @param map
	 *            the map duplicate
	 */
	@SuppressWarnings("unchecked")
	public ArrayMap(Map<? extends K, ? extends V> map) {
		Map.Entry<? extends K, ? extends V> entry;

		size = map.size();
		keys = (K[]) new Object[size];
		values = (V[]) new Object[size];

		Iterator<? extends Map.Entry<? extends K, ? extends V>> entries = map
				.entrySet().iterator();

		for (int i = 0; i < size; i++) {
			entry = entries.next();
			keys[i] = entry.getKey();
			values[i] = entry.getValue();
		}

		modCount = 0;
	}

	@SuppressWarnings("unchecked")
	public void clear() {
		keys = (K[]) new Object[0];
		values = (V[]) new Object[0];
		size = 0;
		modCount++;
	}

	public boolean containsKey(Object key) {
		return indexOf(key, keys, size) != -1;
	}

	public boolean containsValue(Object value) {
		return indexOf(value, values, size) != -1;
	}

	public Set<Map.Entry<K, V>> entrySet() {
		return new AbstractSet<Map.Entry<K, V>>() {

			public Iterator<Map.Entry<K, V>> iterator() {
				return new EntryIterator();
			}

			public int size() {
				return size;
			}

			// the following three methods are strictly speaking
			// not necessary, since AbstractCollection already
			// provides them, but are added for better performance

			public boolean contains(Object object) {
				if (object instanceof Map.Entry) {
					Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
					int pos = indexOf(entry.getKey(), keys, size);
					return pos != -1 && values[pos] == entry.getValue();
				} else {
					return false;
				}
			}

			public boolean remove(Object object) {
				if (object instanceof Map.Entry) {
					Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
					int pos = indexOf(entry.getKey(), keys, size);
					if (pos != -1 && values[pos] == entry.getValue()) {
						remove(pos);
						return true;
					}
				}

				return false;
			}

			public void clear() {
				ArrayMap.this.clear();
			}
		};
	}

	public boolean equals(Object object) {
		if (object instanceof Map) {
			Map<?, ?> otherMap = (Map<?, ?>) object;
			return entrySet().equals(otherMap.entrySet());
		} else {
			return false;
		}
	}

	public V get(Object key) {
		for (int i = 0; i < size; i++) {
			if (keys[i] == key) {
				return values[i];
			}
		}

		return null;
	}

	public int hashCode() {
		Object key, value;
		int keyCode, valueCode;
		int hashCode = 0;

		for (int i = 0; i < size; i++) {
			key = keys[i];
			value = values[i];

			keyCode = key == null ? 0 : key.hashCode();
			valueCode = value == null ? 0 : value.hashCode();

			hashCode += Math.pow(keyCode, valueCode);
		}

		return hashCode;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public Set<K> keySet() {
		return new AbstractSet<K>() {

			public Iterator<K> iterator() {
				return new KeyIterator();
			}

			public int size() {
				return size;
			}

			// the following three methods are strictly speaking
			// not necessary, since AbstractCollection already
			// provides them, but are added for better performance

			public boolean contains(Object object) {
				return containsKey(object);
			}

			public boolean remove(Object object) {
				// done this way to allow null keys!
				int oldSize = size;
				ArrayMap.this.remove(object);
				return size != oldSize;
			}

			public void clear() {
				ArrayMap.this.clear();
			}
		};
	}

	public V put(K key, V value) {
		V result = null;

		int index = indexOf(key, keys, size);
		if (index == -1) {
			if (keys.length == size) {
				keys = (K[]) toLargerArray(keys);
				values = (V[]) toLargerArray(values);
			}

			keys[size] = key;
			values[size] = value;
			size++;
		} else {
			result = values[index];
			values[index] = value;
		}

		modCount++;
		return result;
	}

	public void putAll(Map<? extends K, ? extends V> map) {
		Map.Entry<? extends K, ? extends V> entry;

		Iterator<? extends Map.Entry<? extends K, ? extends V>> entries = map
				.entrySet().iterator();
		while (entries.hasNext()) {
			entry = entries.next();
			put(entry.getKey(), entry.getValue());
		}
	}

	public V remove(Object key) {
		int index = indexOf(key, keys, size);
		if (index == -1) {
			return null;
		}

		V oldValue = values[index];
		remove(index);

		return oldValue;
	}

	public int size() {
		return size;
	}

	public Collection<V> values() {
		return new AbstractCollection<V>() {

			public Iterator<V> iterator() {
				return new ValueIterator();
			}

			public int size() {
				return size;
			}

			// the following two methods are strictly speaking
			// not necessary, since AbstractCollection already
			// provides them, but are added for better performance

			public boolean contains(Object object) {
				for (int i = 0; i < size; i++) {
					if (values[i] == object) {
						return true;
					}
				}
				return false;
			}

			public boolean remove(Object object) {
				int index = indexOf(object, values, size);
				if (index == -1) {
					return false;
				} else {
					remove(index);
					return true;
				}
			}

			public void clear() {
				ArrayMap.this.clear();
			}
		};
	}

	/**
	 * Get the key at the specified index in the map.
	 * 
	 * @param index
	 *            the index
	 * @return the key at the specified index in the map
	 */
	public K getKey(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("invalid index");
		}
		return keys[index];
	}

	/**
	 * Get the value at the specified index in the map.
	 * 
	 * @param index
	 *            the index
	 * @return the value at the specified index in the map
	 */
	public V getValue(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("invalid index");
		}
		return values[index];
	}

	@SuppressWarnings("unchecked")
	private <T> T[] toLargerArray(T[] array) {
		int oldSize = array.length;
		T[] result = (T[]) Array.newInstance(array.getClass()
				.getComponentType(), oldSize + 1);
		System.arraycopy(array, 0, result, 0, oldSize);
		return result;
	}

	private int indexOf(Object object, Object[] array, int length) {
		for (int i = 0; i < length; i++) {
			if (array[i] == object) {
				return i;
			}
		}

		return -1;
	}

	private void remove(int index) {
		// move all elements one position to the left, and set the last to null
		int nextIndex = index + 1;
		int remainingLength = size - nextIndex;

		System.arraycopy(keys, nextIndex, keys, index, remainingLength);
		System.arraycopy(values, nextIndex, values, index, remainingLength);

		size--;
		keys[size] = null;
		values[size] = null;

		modCount++;
	}

	public String toString() {
		StringBuilder buffer = new StringBuilder();
		buffer.append('{');

		Iterator<Map.Entry<K, V>> i = entrySet().iterator();
		boolean hasNext = i.hasNext();

		while (hasNext) {
			Map.Entry<K, V> e = i.next();

			K key = e.getKey();
			if (key == this) {
				buffer.append("(this Map)");
			} else {
				buffer.append(key);
			}

			buffer.append('=');

			V value = e.getValue();
			if (value == this) {
				buffer.append("(this Map)");
			} else {
				buffer.append(value);
			}

			hasNext = i.hasNext();
			if (hasNext) {
				buffer.append(", ");
			}
		}

		buffer.append('}');
		return buffer.toString();
	}

	public class Entry implements Map.Entry<K, V> {

		private int index;

		public Entry(int index) {
			this.index = index;
		}

		public K getKey() {
			return keys[index];
		}

		public V getValue() {
			return values[index];
		}

		public V setValue(V object) {
			V oldValue = values[index];
			values[index] = object;
			return oldValue;
		}

		public boolean equals(Object object) {
			if (object instanceof Map.Entry) {
				Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
				boolean keyOK = keys[index] == null ? entry.getKey() == null
						: keys[index] == entry.getKey();
				boolean valueOK = values[index] == null ? entry.getValue() == null
						: values[index] == entry.getValue();
				return keyOK && valueOK;
			} else {
				return false;
			}
		}

		public int hashCode() {
			Object key = keys[index];
			Object value = values[index];

			int keyCode = key == null ? 0 : key.hashCode();
			int valueCode = value == null ? 0 : value.hashCode();

			return (int) Math.pow(keyCode, valueCode);
		}

		public String toString() {
			StringBuilder buffer = new StringBuilder(50);
			buffer.append('[');
			buffer.append(keys[index].toString());
			buffer.append(',');
			buffer.append(values[index].toString());
			buffer.append(']');
			return buffer.toString();
		}
	}

	private class EntryIterator implements Iterator<Map.Entry<K, V>> {

		private int index;

		private int expectedModCount;

		public EntryIterator() {
			index = 0;
			expectedModCount = modCount;
		}

		public boolean hasNext() {
			return index < size;
		}

		public Map.Entry<K, V> next() {
			if (index >= size) {
				throw new NoSuchElementException();
			}

			if (modCount != expectedModCount) {
				throw new ConcurrentModificationException();
			}

			Entry result = new Entry(index);
			index++;
			return result;
		}

		public void remove() {
			if (index == 0) {
				// 'next' has not been invoked yet
				throw new IllegalStateException();
			}

			if (modCount != expectedModCount) {
				throw new ConcurrentModificationException();
			}

			ArrayMap.this.remove(index - 1);
			expectedModCount++;
		}
	}

	private class ArrayIterator<T> implements Iterator<T> {

		// TODO: class implementation looks very similar to EntryIterator: share
		// some code?

		private T[] array;

		private int length;

		private int index;

		private int expectedModCount;

		public ArrayIterator(T[] array, int length) {
			this.array = array;
			this.length = length;
			index = 0;
			expectedModCount = modCount;
		}

		public boolean hasNext() {
			return index < length;
		}

		public T next() {
			if (index >= length) {
				throw new NoSuchElementException();
			}

			if (modCount != expectedModCount) {
				throw new ConcurrentModificationException();
			}

			T result = array[index];
			index++;
			return result;
		}

		public void remove() {
			if (index == 0) {
				// 'next' has not been invoked yet
				throw new IllegalStateException();
			}

			if (modCount != expectedModCount) {
				throw new ConcurrentModificationException();
			}

			ArrayMap.this.remove(index - 1);
			length--;
			expectedModCount++;
		}
	}

	private class KeyIterator extends ArrayIterator<K> {

		public KeyIterator() {
			super(keys, size);
		}
	}

	private class ValueIterator extends ArrayIterator<V> {

		public ValueIterator() {
			super(values, size);
		}
	}
}
